[BAEKJOON] 10836. 여왕벌

문제 :

link : https://www.acmicpc.net/problem/10836

문제가 복잡해서 링크를 확인하자 !

입력 :

입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 줄에는 첫날부터 순서대로 제일 왼쪽 열과 제일 위쪽 행의 애벌레들이 자라는 정도가 다음의 형식으로 주어진다. 본문에서 보인 것과 같이, 자라는 크기를 제일 왼쪽 아래 칸에서 시작해서 위쪽으로 올라가서 제일 위쪽에 도착하면 오른쪽으로 이동하며 읽었다고 하자. 이 값들은 감소하지 않는다. 따라서, 이 수열을 처음부터 읽었을 때 0의 개수, 1의 개수, 2의 개수를 순서대로 입력에 준다. 하루에 대해서 이 세 개수들의 합은 2M-1임이 자명하다. 세 값들 중에 0이 있을 수 있다

출력 :

M개의 줄에 각각 M개의 자연수를 출력한다. 이는 각 애벌레의 마지막 날 저녁의 크기를 첫 행부터, 각 행에서는 왼쪽부터 제시한 것이다. (본문의 예와 동일한 형태이다.)

풀이 :

진짜 알고리즘은 풀면 풀수록 어려운 문제가 많은 듯 하다. 이 문제도 간단하게 생각하면 풀리지 않는 문제였다.

우선 격자판 자체가 700*700 이면서 날짜 수가 백만 이하의 반복이 일어나기 때문에 일반적으로 구현하게 되면 무조건 시간초과가 일어나게 된다.

이문제에서는 크게 두 가지의 포인트를 구현해야 시간초과를 피할 수 있다.

1. 멘 왼쪽과 위쪽 인덱스를 제외한 인덱스 칸에서는 왼쪽, 왼쪽 위, 위쪽 인덱스 값 중 가장 큰 성장값으로 더해주어야 하는데 굳이 이렇게 구현할 필요가 없다. 성장값은 매번 오름차순으로 성장하기 때문에 가장 위쪽 인덱스의 성장값으로만 매번 더해주면 된다.
2. 성장값은 0, 1, 2 성장 값의 갯수로 주어지는데 모두 저장해줄 필요가 없다. 0→1 로 변하는 시작구간과 1→2로 변하는 시작구간만 매번 기록해두고 마지막에 모두 합쳐서 계산해 주어야 한다.

특별한 알고리즘을 사용하는 문제는 아니지만 문제를 많이 풀어보고 새롭게 문제에 접근하는 실력을 키울 필요가 있을 듯 하다.

코드 :

#include <iostream>

using namespace std;
int map[700][700];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, i, j, num, cur;
    cin >> n >> m;
    for (i = 0; i < n; i++)
        fill_n(map[i], n, 1);
    int *dp = new int[2 * n]{0};
    while (m--) {
        cur = 0;
        for (i = 0; i < 3; i++) {
            cin >> num;
            cur += num;
            dp[cur]++;
        }
    }
    cur = 0;
    num = 0;
    for (i = n - 1; i >= 0; i--) {
        num += dp[cur];
        map[i][0] = num + 1;
        cur++;
    }
    for (i = 1; i < n; i++) {
        num += dp[cur];
        map[0][i] = num + 1;
        cur++;
    }
    for (i = 1; i < n; i++)
        for (j = 1; j < n; j++)
            map[i][j] = map[0][j];
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            cout << map[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}